---
title: "密文搜索"
created: 2025-11-28
tags:
  - 算法
---

# 密文搜索

## 题目 [密文搜索](https://www.lanqiao.cn/problems/138/learning/)

![[image-d0d04f10.png]]

## 思路分析

在长度1024\*1024的母串中 找n种长度为8的子串的全排列出现几次

暴力做的话 思路就是 把n个串的每个可能排列都在母串中find 注意一个问题 同一个子串可能在母串中出现多次 所以找到一个后不能立即退出 而是在找到的位置继续往后find
n范围1000 长度为8 8的全排列有8!=40320种可能 也就是说共要枚举40320000次 还得find 肯定会超时 事实也是过了4/5

可以借鉴最小表示法的思路 用排序后的串表示串本身 然后直接哈希做

注意一个问题 最小表示法是在 循环同构的串的场景下  限制比这题要多些 这题是说任意顺序 也就是说 只要长度一定 出现的单词一样
就是合法的 而循环同构还有一个顺序的限制（只能以每个单词为开头的长度固定的串） 所以对于这题来说 只需要限制长度 做一遍sort 得到一个简化版的“最小表示法”
如果相同 就说明合法 ++

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=1010;
string og;
string tr[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> og;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> tr[i];
    }
    LL cnt = 0;
    for (int i = 0; i < n; i++) {
        sort(tr[i].begin(), tr[i].end());  // 确保字符串按字典序排列，以便遍历所有排列
        do {
            size_t pos = og.find(tr[i], 0);  // 从位置0开始搜索
            while (pos != string::npos) {    // 搜索整个字符串中的所有匹配
                cnt++;
                pos = og.find(tr[i], pos + 1);  // 从下一个位置继续搜索 一个子串可能在模式串里出现多次 不能忽视这个
            }
        } while (next_permutation(tr[i].begin(), tr[i].end()));
    }
    cout << cnt;
    return 0;
}
```

```cpp
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int ans = 0;
    string s;
    int n;
    map<string, int> m1;
    cin >> s >> n;
    if (s.size() < 8)
        return 0;
    for (int i = 0; i < n; i++) {
        string s1;
        cin >> s1;
        sort(s1.begin(), s1.end());
        m1[s1]++;//每个字符串都是键 值都是他们在后面n行中出现的次数
    }
    for (int i = 0; i < s.size() - 7; i++) {
        string s2;
        s2 = s.substr(i, 8); //每次从第i位开始切割切割8位
        sort(s2.begin(), s2.end());
        if (m1[s2]) { //在m1中搜索是否有相同的字符串
            ans = ans + m1[s2];//这里加上该字符串键对应的值
        }
    }
    cout << ans;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[完美正方形|完美正方形]] 🏠 [[00-冲刺国赛]] ➡️ [[居民聚会|居民聚会]]